// https://www.lintcode.com/problem/bomb-enemy/my-submissions

class Solution {
public:
    /**
     * @param grid: Given a 2D grid, each cell is either 'W', 'E' or '0'
     * @return: an integer, the maximum enemies you can kill using one bomb
     */
     
    // 时间O(MN) 空间O(MN) (不能用滚动数组，最后加起来需要每个格子的值)
    int maxKilledEnemies(vector<vector<char>> &grid) {
        if (grid.empty()) return 0;
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> up(m, vector<int>(n, 0)); 
        vector<vector<int>> down(m, vector<int>(n, 0)); 
        vector<vector<int>> left(m, vector<int>(n, 0)); 
        vector<vector<int>> right(m, vector<int>(n, 0)); 
        
        // up
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (grid[i][j] == 'W') 
                {
                    up[i][j] = 0;
                    continue;
                }
                else if (grid[i][j] == 'E')
                {
                    up[i][j]++;
                }
                if (i > 0)
                {
                    up[i][j] += up[i - 1][j];
                }
            }
        }
        
        // left
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (grid[i][j] == 'W') 
                {
                    left[i][j] = 0;
                    continue;
                }
                else if (grid[i][j] == 'E')
                {
                    left[i][j]++;
                }
                if (j > 0)
                {
                    left[i][j] += left[i][j - 1];
                }
            }
        }
        
        // down
        for (int i = m - 1; i >= 0; --i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (grid[i][j] == 'W') 
                {
                    down[i][j] = 0;
                    continue;
                }
                else if (grid[i][j] == 'E')
                {
                    down[i][j]++;
                }
                if (i < m - 1)
                {
                    down[i][j] += down[i + 1][j];
                }
            }
        }
        
        // right
        for (int i = 0; i < m; ++i)
        {
            for (int j = n - 1; j >= 0; --j)
            {
                if (grid[i][j] == 'W') 
                {
                    right[i][j] = 0;
                    continue;
                }
                else if (grid[i][j] == 'E')
                {
                    right[i][j]++;
                }
                if (j < n - 1)
                {
                    right[i][j] += right[i][j + 1];
                }
            }
        }
        
        
        int maxVal = 0;
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (grid[i][j]  == '0') maxVal = max(maxVal, 
                    up[i][j] + down[i][j] + left[i][j] + right[i][j]);
            }
        }
        return maxVal;
    }
};